package array;

public class MaxBitonic {

	/*
	 * Given an array A[0 ... n-1] containing n positive integers, a subarray
	 * A[i ... j] is bitonic if there is a k with i <= k <= j such that A[i] <=
	 * A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j - 1] > = A[j]. Write a
	 * function that takes an array as argument and returns the length of the
	 * maximum length bitonic subarray. Expected time complexity of the solution
	 * is O(n)
	 * 
	 * Simple Examples 1) A[] = {12, 4, 78, 90, 45, 23}, the maximum length
	 * bitonic subarray is {4, 78, 90, 45, 23} which is of length 5.
	 * 
	 * 2) A[] = {20, 4, 1, 2, 3, 4, 2, 10}, the maximum length bitonic subarray
	 * is {1, 2, 3, 4, 2} which is of length 5.
	 * 
	 * Extreme Examples 1) A[] = {10}, the single element is bitnoic, so output
	 * is 1.
	 * 
	 * 2) A[] = {10, 20, 30, 40}, the complete array itself is bitonic, so
	 * output is 4.
	 * 
	 * 3) A[] = {40, 30, 20, 10}, the complete array itself is bitonic, so
	 * output is 4.
	 */

	public static int botonic(int[] array) {
		int i = 0;
		int n = array.length;
		int[] incr = new int[n];
		int[] decr = new int[n];
		int max = 0;

		incr[0] = 1;
		decr[n - 1] = 1;
		for (i = 1; i < n; i++) {
			if (array[i] > array[i - 1])
				incr[i] = incr[i - 1] + 1;
			else
				incr[i] = 1;
		}
		for (i = n - 2; i >= 0; i--) {
			if (array[i] > array[i + 1])
				decr[i] = decr[i + 1] + 1;
			else
				decr[i] = 1;
		}

		max = incr[0] + decr[0] - 1;
		for (i = 1; i < n; i++) {
			if (incr[i] + decr[i] - 1 > max)
				max = incr[i] + decr[i] - 1;
		}
		return max;

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] arr = { 12, 4, 78, 90, 45, 23 };
		System.out.println(botonic(arr));
	}

}
